package algorithm.leetcode.I1001to1200;

import java.util.Arrays;

/**
 * 给出一个正数组,添加 D-1 个分割点,将数组切分为 D 个子数组
 * 返回 D 个子数组可能的最小和
 *
 * 背答案吧,思路太tm秀了,我不看答案根本想不到,本质:二分搜索
 *
 * 设所求为 x
 * 那么x必须满足:任何大于x的运力都可以满足D天内完成运输的要求, 并且任何小于x的运力都无法满足D天内完成运输的要求
 * 因此可以设定一个最高运力(一般是整个数组的求和sum),和一个最低运力(这个随意,可以是数组的最大值,也可以是0),然后开始二分查找
 *
 * tricky的地方在于,获取mid之后通过怎样的逻辑变换low和high
 */

public class Q1011 {

    public int shipWithinDays(int[] weights, int D) {
        int high = Arrays.stream(weights).sum();
        int low = 0;

        while (low < high) {
            int mid = ((high-low)>>1)+low;
            // 如果mid可以运输,那么尝试更小的mid,mid本身要放进去,因为可能是解
            if (ifCanTransfer(weights, D, mid)) high = mid;
            // 如果mid不可以运输,那么尝试更大的mid,mid本身不可能是解
            else low = mid+1;
        }
        return low;
    }

    /**
     * 本题的难点,核心就在于原始数组是不可被打乱的,故可以写出这样的check方法
     * @param weight 原weight数组
     * @param D 原给定的天数上限
     * @param V 你要测试的运力
     * @return 待测试的运力是否满足要求
     */
    private static boolean ifCanTransfer(int[] weight, int D, int V) {
        int days = 1;
        int windowWeightSum = 0;
        for (int i = 0; i < weight.length; i++) {
            if (weight[i] > V) return false;  // 注意这一行,绝对不能少
            else if (windowWeightSum + weight[i] <= V) windowWeightSum += weight[i];
            else {
                windowWeightSum = weight[i];
                days++;
            }
        }
        return days <= D;
    }

    public static void main(String[] args) {
        Q1011 q1011 = new Q1011();
        System.out.println(q1011.shipWithinDays(new int[]{1, 2, 3, 1, 1}, 4));
    }

}
